package com.itheima.api.array.demo02;

public class SortDemo01 {

    // 入口
    public static void main(String[] args) {

        // 定义一个数组
        int[] arr = {12 , 34 , 56 , 11 , 10 , 9} ;

        // 调用printArr方法
        printArr(arr);
        System.out.println();

        // 排序
//        bubbleSort(arr);
        quickSort(arr , 0 , arr.length - 1);

        // 调用printArr方法
        printArr(arr);

    }

    // 进行快速排序的方法
    public static  void quickSort(int[] arr , int minIndex , int maxIndex) {

        if(minIndex < maxIndex) {
            int partitionIndex = partition(arr, minIndex, maxIndex);

            // 对左分区进行快排操作
            quickSort(arr , minIndex  , partitionIndex - 1) ;

            // 对右分区进行快速排序操作
            quickSort(arr , partitionIndex + 1 , maxIndex);
        }

    }

    /**
     * 这个方法的主要作用就是进行分区操作，参数
     * arr：         要分区的数组
     * minIndex      指定分区的范围
     * maxIndex      指定分区的范围
     * @param arr
     * @param minIndex
     * @param maxIndex
     * @return
     */
    public static int partition(int[] arr , int minIndex , int maxIndex) {

        // 选定的一个基准数,一般情况下，我们都是使用数组的第一个元素作为基准数
        int temp = arr[minIndex] ;

        while(minIndex < maxIndex) {

            // 从右往左查找第一个小于基准数的数对应的索引，需要使用循环； 循环的结束条件  arr[maxIndex] < temp
            // 当前arr[maxIndex] >= temp的时候需要一直进行查找
            while(arr[maxIndex] >= temp && minIndex < maxIndex) {
                maxIndex--;
            }

            // 使用maxIndex所对应的元素进行填坑
            if(minIndex < maxIndex) {
                arr[minIndex] = arr[maxIndex] ;
                minIndex++;
            }

            // 从左往右进行查找，查找第一个大于等于基准数的数对应的索引，需要使用循环进行查找；循环的结束条件：arr[minIndex] >= temp
            // 当arr[minIndex] < temp 一直进行查找操作
            while(arr[minIndex] < temp && minIndex < maxIndex) {
                minIndex++;
            }

            // 使用minIndex所对应的元素值进行填坑操作
            if(minIndex < maxIndex) {
                arr[maxIndex] = arr[minIndex] ;
                maxIndex--;
            }

        }

        // 使用基准数进行填坑操作
        arr[maxIndex] = temp ;

        // 返回这个分区的临界索引值
        return maxIndex ;

    }


    // 遍历数组的方法
    public static void printArr(int[] arr){

        for(int x = 0 ; x < arr.length ; x++) {
            System.out.print(arr[x] + " ");
        }

    }

    // 冒泡排序
    public static void bubbleSort(int[] arr) {

        for(int y = 0 ; y < arr.length - 1 ; y++) {

            // 第一次排序操作
            for(int x = 0 ; x < arr.length - 1 - y; x++) {
                if(arr[x] > arr[x+1]) {
                    int temp = arr[x] ;
                    arr[x] = arr[x + 1] ;
                    arr[x + 1] = temp ;
                }
            }

        }

//        // 第一次排序操作
//        for(int x = 0 ; x < arr.length - 1 - 0; x++) {
//            if(arr[x] > arr[x+1]) {
//                int temp = arr[x] ;
//                arr[x] = arr[x + 1] ;
//                arr[x + 1] = temp ;
//            }
//        }
//
//        // 第二次排序操作
//        for(int x = 0 ; x < arr.length - 1 - 1; x++) {
//            if(arr[x] > arr[x+1]) {
//                int temp = arr[x] ;
//                arr[x] = arr[x + 1] ;
//                arr[x + 1] = temp ;
//            }
//        }
//
//        // 第三次排序操作
//        for(int x = 0 ; x < arr.length - 1 - 2; x++) {
//            if(arr[x] > arr[x+1]) {
//                int temp = arr[x] ;
//                arr[x] = arr[x + 1] ;
//                arr[x + 1] = temp ;
//            }
//        }
//
//        // 第四次排序操作
//        for(int x = 0 ; x < arr.length - 1 - 3; x++) {
//            if(arr[x] > arr[x+1]) {
//                int temp = arr[x] ;
//                arr[x] = arr[x + 1] ;
//                arr[x + 1] = temp ;
//            }
//        }
//
//        // 第五次排序操作
//        for(int x = 0 ; x < arr.length - 1 - 4; x++) {
//            if(arr[x] > arr[x+1]) {
//                int temp = arr[x] ;
//                arr[x] = arr[x + 1] ;
//                arr[x + 1] = temp ;
//            }
//        }

    }

}
